package com.ly.algorithm.leetcode.tree;

/**
 * @Classname Problem701
 * @Description
 * 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
 *
 * 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
 *
 *  
 *
 * 例如, 
 *
 * 给定二叉搜索树:
 *
 *         4
 *        / \
 *       2   7
 *      / \
 *     1.txt   3
 *
 * 和 插入的值: 5
 * 你可以返回这个二叉搜索树:
 *
 *          4
 *        /   \
 *       2     7
 *      / \   /
 *     1.txt   3 5
 * 或者这个树也是有效的:
 *
 *          5
 *        /   \
 *       2     7
 *      / \
 *     1.txt   3
 *          \
 *           4
 *

 * @Date 2020/9/30 21:46
 * @Author 冷心影翼
 */
public class Problem701 {

	public static void main(String[] args) {

		Solution701 solution701 = new Solution701();
		TreeNode treeNode = new TreeNode(4);
		treeNode.left  = new TreeNode(2);
		treeNode.left.left  = new TreeNode(1);
		treeNode.left.right  = new TreeNode(3);
		treeNode.right =  new TreeNode(7);
		TreeNode treeNode1 = solution701.insertIntoBST(null, 5);
		System.out.println(treeNode1.val);
	}

}


class Solution701 {

	public TreeNode insertIntoBST(TreeNode root, int val) {
		if(root == null)
			return new TreeNode(val);
		preOrder(root,val);
		return root;
	}

	public void preOrder(TreeNode root, int val) {
		if(root == null)

			return;
		if(root.left == null && root.val>val) {
			root.left = new TreeNode(val);
			return;
		}
		if(root.right == null && root.val<val) {
			root.right = new TreeNode(val);
			return;
		}
		if(root.val>val)
			preOrder(root.left,val);
		if(root.val<val)
			preOrder(root.right,val);
	}
}